This invention relates generally to broadcasting packets in a communications network including switches, and more particularly to avoiding deadlock during a broadcast of packets.
One type of local area mesh-connected network that can be used to broadcast message packets is called a cut-through network. In a cut-through network, switches forward packets from sources to destinations without necessarily storing complete packets in switch buffers at any point in time. Cut-through networks are contrasted with traditional store-and-forward networks where each packet is fully buffered in each switch through which the packet passes.
Cut-through networks offer advantages in performance and cost. A cut-through network is logically represented by a spanning tree. A spanning tree can be represented as a graph of nodes and edges, where the nodes represent the switches and the edges represent the links between the switches. Point-to-point packets can be forwarded both on links and on cross-links. Cross-links are links that are not part of the spanning tree. The use of all links, including cross-links, offers advantages in utilization for point-to-point communication.
One cut-through network is the xe2x80x9cAN1xe2x80x9d network, originally known as xe2x80x9cAutonet.xe2x80x9d This cut-through network is a high-speed self-configuring local area network. This cut-through network is described by Schroeder et al. in xe2x80x9cAutonet: A High-speed, Self-configuring Local Area Network Using Point-to-Point Links,xe2x80x9d SRC Research Report 59, Apr. 30, 1990. See also, Schroeder et al., xe2x80x9cHigh-speed Mesh-connected Local Area Network,xe2x80x9d U.S. Pat. No. 5,088,091, issued Feb. 11, 1992.
In a cut-through network such as the Autonet, broadcast packets are directly forwarded xe2x80x9cupxe2x80x9d the spanning tree to the root switch, and from there the broadcast packet is xe2x80x9cfloodedxe2x80x9d xe2x80x9cdownxe2x80x9d the spanning tree to all destinations. Cross-links are not used. Here, flooding means that the broadcast packet is replicated on all spanning tree links leading xe2x80x9cdownwardxe2x80x9d out of a switch. The terms up and down are used to indicate that the links in the spanning tree have some determinable ordering.
The AN1 or Autonet network avoids deadlocks by placing restrictions on when broadcast packet can be stopped, and ensuring that the buffers are big enough to hold all of any broadcast packet. For non-broadcast packets it may be inconvenient or impractical to place a limit on their lengths. The prior approach limits the maximum length of broadcast packets to no more than xc2xd of the buffer size at switches. The limit on broadcast packets complicates host and bridge network software, especially if the maximum length of a broadcast packet is less than the maximum length of a non-broadcast packet. The minimum requirement of buffer space can make the switches more expensive. The deadlock problems of the prior art network are described in detail in Section 6.6.6 of SRC Research Report 59.
Therefore, there is a need for a network that avoids deadlock during the broadcast of packets without having any size restrictions on buffers used in the network to store the packets during the broadcast.
The invention provides a method for broadcasting packets in a network including a plurality of switches. The network is a cut-through network that can logically be represented by a spanning tree and cross-links.
A broadcast packet is directly sent from an originating switch to the root switch of the network. At this point the root switch can be considered the current switch.
Copies of the packet are sent from the current switch to all descendant switches when all copies of the packet have been received in the current switch to avoid deadlock during the broadcasting of the packets. Descendant switches are those switches that are connected by downward directed links from the current switch. A downward directed link can be a spanning tree link or a cross-link.
In one aspect of the invention, the current switch simultaneously sends the copies of the packet to the descendant switches. In another aspect, the copies of the packet sent on cross-links are represented by tokens identifying the packet.
In case of a network failure the network is initialized by propagating an initialization state to all switches, collecting the network topology, distributing the network topology to all switches, and waiting until all switches are initialized before resuming operation.